package com.itheima.Array.sort;

import java.util.Arrays;

/**
 * @Author: Ethan Yankang
 * @Program: code-random-recordings
 * @Date: 2024-08-19 16:28
 **/
public class RadixSort {



    // 基数排序
    public static void radixSort(int[] nums) {
        int n = nums.length;
        int maxDigits = getMaxDigits(nums);

        int[] output = new int[n];
        int[] count = new int[10];

        int placeValue = 1; // 初始为个位，依次提升到十位、百位...
        for (int d = 0; d < maxDigits; d++) {

            Arrays.fill(count, 0); // 计数器归零

            // 统计当前位的数字频率
            for (int num : nums) {
                int digit = (num / placeValue) % 10;
                count[digit]++;
            }

            // 累积频率，确定每个数字的最终位置
            for (int i = 1; i < 10; i++) {
                count[i] += count[i - 1];
            }

            // 按当前位的数字排序
            for (int i = n - 1; i >= 0; i--) {
                int digit = (nums[i] / placeValue) % 10;
                output[count[digit] - 1] = nums[i];
                count[digit]--;
            }

            // 更新数组
            System.arraycopy(output, 0, nums, 0, n);

            placeValue *= 10; // 移动到下一位
        }
    }

    // 获取数组中最大数的位数
    private static int getMaxDigits(int[] nums) {
        int max = Arrays.stream(nums).max().getAsInt();
        return Integer.toString(max).length();
    }
}
